package DynamicProgramming;

/**
 * 动态规划解决0-1背包问题
 *
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2020/12/16 19:20
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        findMax();
        findWhat(number, capacity);
//        findMaxBetter();

        for (int i = 1; i <= number; i++) {
            System.out.println(item[i]);
        }
    }

    static final int number = 4;//物品数
    static final int capacity = 8;//背包大小
    static final int[] w = {0, 2, 3, 4, 5};            //商品的体积2、3、4、5
    static final int[] v = {0, 3, 4, 5, 6};            //商品的价值3、4、5、6

    static int[][] V = new int[number + 1][capacity + 1]; //动态规划表
    static int[] item = new int[number + 1];

    /**
     * 动态规划:填表
     * <p>
     * V[i - 1][j]：未放入物品i时的最大价值；
     * <p>
     * V[i - 1][j - w[i]] + v[i]) ：放入当前物品后的最大价值；
     * V[i - 1][j - w[i]]: 放入当前物品后，剩余空间所能放入的，最大价值；
     * j - w[i]：放入当前物品i，剩余空间；
     * v[i]:当前物品价值；
     */
    static void findMax() {
        int i, j;
        // 填表
        for (i = 1; i <= number; i++) {
            for (j = 0; j <= capacity; j++) {
                if (j < w[i]) { // 背包装不进
                    V[i][j] = V[i - 1][j];
                } else { // 能装
                    if (V[i - 1][j] > V[i - 1][j - w[i]] + v[i]) { // 不装价值大
                        V[i][j] = V[i - 1][j]; // 总价值不变
                    } else { // i-1个物品的最优解与第i个物品的价值之和更大
                        V[i][j] = V[i - 1][j - w[i]] + v[i]; //填入当前最大值
                    }
                }
            }
        }
    }

    /**
     * 找解的组成方式：
     * 从最优解开始查找当前第i个商品是否被装入
     * V(i,j)=V(i-1,j)时，说明没有选择第i 个商品，则回到V(i-1,j)
     *
     * @param i 矩阵行（第i个商品）
     * @param j 矩阵列（背包空间大小j）
     */
    static void findWhat(int i, int j) {
        if (i > 0) {
            if (V[i][j] == V[i - 1][j]) {// 未装入物品i（总价值未发生变化）
                item[i] = 0; //标记
                findWhat(i - 1, j); // 查看下一物品是否装入
            } else if (j - w[i] >= 0 && V[i][j] == V[i - 1][j - w[i]] + v[i]) {
                item[i] = 1;//标记已被选中
                findWhat(i - 1, j - w[i]);//回到装包之前的位置
            }

        }
    }

    static int[] B = new int[capacity + 1];
    /**
     * 空间优化:将V使用一维数组存储
     * 每一次V(i)(j)改变的值只与V(i-1)(x) {x:1...j}有关，V(i-1)(x)是前一次i循环保存下来的值；
     * 因此，可以将V缩减成一维数组，从而达到优化空间的目的，状态转移方程转换为 B(j)= max{B(j), B(j-w(i))+v(i)}；
     */
    static void findMaxBetter() {
        int i, j;
        for (i = 1; i <= number ; i++) { // 放入物品
            for (j = capacity; j >= 0; j--) {
                if (j - w[i] >= 0 && B[j] <= B[j - w[i]] + v[i]) {
                    B[j] = B[j - w[i]] + v[i];
                }
            }
        }
    }


}
